package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         93,
		Discription: "数字字符串映射到IP的种类数",
		Level:       2,
		Labels: map[string]int{
			"递归": 1,
		},
	})
}

func RestoreIpAddresses(s string) []string {
	res := make([]string, 0)
	var travel func(int, int, string)
	//字符串开始的索引，目前已有的IP位数（总共4），已拼接的IP字符串
	travel = func(start int, count int, str string) {
		if start == len(s) && count == 4 {
			res = append(res, str[:len(str)-1])
			return
		}

		//长度不够用或长度用完了
		if start >= len(s) || count >= 4 {
			return
		}

		//首位为0，那当前位只能为0
		if s[start] == '0' {
			travel(start+1, count+1, str+"0.")
			return
		}

		//一位
		travel(start+1, count+1, str+s[start:start+1]+".")

		//二位
		if start <= len(s)-2 {
			travel(start+2, count+1, str+s[start:start+2]+".")
		}

		//三位
		if start <= len(s)-3 {
			//首位为1肯定有效
			if s[start] == '1' {
				travel(start+3, count+1, str+s[start:start+3]+".")
				return
			}

			if s[start:start+3] >= "200" && s[start:start+3] <= "255" {
				travel(start+3, count+1, str+s[start:start+3]+".")
			}
		}
	}

	travel(0, 0, "")
	return res
}
